{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sum of Root To Leaf Binary Numbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sumRootToLeaf"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #从根到叶的二进制数之和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给出一棵二叉树，其上每个结点的值都是&nbsp;<code>0</code>&nbsp;或&nbsp;<code>1</code>&nbsp;。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，如果路径为&nbsp;<code>0 -&gt; 1 -&gt; 1 -&gt; 0 -&gt; 1</code>，那么它表示二进制数&nbsp;<code>01101</code>，也就是&nbsp;<code>13</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>对树上的每一片叶子，我们都要找出从根到该叶子的路径所表示的数字。</p>\n",
    "\n",
    "<p>返回这些数字之和。题目数据保证答案是一个 <strong>32 位 </strong>整数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2019/04/04/sum-of-root-to-leaf-binary-numbers.png\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,0,1,0,1,0,1]\n",
    "<strong>输出：</strong>22\n",
    "<strong>解释：</strong>(100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [0]\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中的节点数在&nbsp;<code>[1, 1000]</code>&nbsp;范围内</li>\n",
    "\t<li><code>Node.val</code>&nbsp;仅为 <code>0</code> 或 <code>1</code>&nbsp;</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sum-of-root-to-leaf-binary-numbers](https://leetcode.cn/problems/sum-of-root-to-leaf-binary-numbers/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sum-of-root-to-leaf-binary-numbers](https://leetcode.cn/problems/sum-of-root-to-leaf-binary-numbers/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,0,1,0,1,0,1]', '[0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(node, val):\n",
    "            if node is None:\n",
    "                return 0\n",
    "            val = (val<<1) | node.val\n",
    "            if node.left is None and node.right is None:\n",
    "                return val\n",
    "            return dfs(node.left,val)+dfs(node.right,val)\n",
    "        return dfs(root, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        total, pre_sum = 0, 0\n",
    "        curr, stack = root, []\n",
    "        prev = None\n",
    "        while curr or stack:\n",
    "            while curr:\n",
    "                pre_sum = (pre_sum << 1) | curr.val\n",
    "                stack.append(curr)\n",
    "                curr = curr.left\n",
    "            curr = stack[-1]\n",
    "            if not curr.right or curr.right == prev:\n",
    "                # 如果当前节点为叶结点\n",
    "                if not (curr.left or curr.right):\n",
    "                    total += pre_sum\n",
    "                pre_sum >>= 1\n",
    "                stack.pop()\n",
    "                prev = curr\n",
    "                curr = None\n",
    "            else:\n",
    "                curr = curr.right\n",
    "\n",
    "        return total   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        # 這題好難唷...\n",
    "        # recursive (top-down)\n",
    "        def dfs(node, cur_sum):\n",
    "            if not node: return 0\n",
    "\n",
    "            cur_sum = (2*cur_sum) + node.val\n",
    "\n",
    "            if node.left or node.right:\n",
    "                return dfs(node.left, cur_sum) + dfs(node.right, cur_sum)\n",
    "            else:\n",
    "                return cur_sum\n",
    "        return dfs(root, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        def dfs(node, res):\n",
    "            if node:\n",
    "                res = res * 2 + node.val\n",
    "                if not node.left and not node.right:\n",
    "                    nonlocal ans\n",
    "                    ans += res\n",
    "                else:\n",
    "                    dfs(node.left, res)\n",
    "                    dfs(node.right, res)\n",
    "        dfs(root, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(node,val):\n",
    "            if not node:return 0\n",
    "            #先<<1扩大2倍  在进行或运算  将这次的那个node节点的值给拿到\n",
    "            val=val<<1| node.val#先拿到这个节点的数值\n",
    "            if not node.left and not node.right:return val#叶子结点\n",
    "            return dfs(node.left,val)+dfs(node.right,val)\n",
    "        return dfs(root,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = 0\n",
    "        self.path = []\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        self.traverse(root)\n",
    "        return self.res\n",
    "    def traverse(self,root):\n",
    "        if(root==None):\n",
    "            return \n",
    "        self.path.append(str(root.val))\n",
    "        if(root.left==None and root.right==None):\n",
    "            s = (\"\".join(self.path))\n",
    "            self.res += int(s,2)\n",
    "        self.traverse(root.left)\n",
    "        self.traverse(root.right)\n",
    "        self.path.pop()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(node: Optional[TreeNode], val: int) -> int:\n",
    "            if node is None:\n",
    "                return 0\n",
    "            val = (val << 1) | node.val\n",
    "            if node.left is None and node.right is None:\n",
    "                return val\n",
    "            return dfs(node.left, val) + dfs(node.right, val)\n",
    "        return dfs(root, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        # 這題好難唷...\n",
    "        # recursive (top-down)\n",
    "        def dfs(node, cur_sum):\n",
    "            if not node: return 0\n",
    "\n",
    "            cur_sum = (2*cur_sum) + node.val # 要想到這點太難了...\n",
    "\n",
    "            if node.left or node.right:\n",
    "                return dfs(node.left, cur_sum) + dfs(node.right, cur_sum)\n",
    "            else:\n",
    "                return cur_sum\n",
    "        return dfs(root, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        def dfs(root,r):\n",
    "            if root:\n",
    "                val = (r << 1) + root.val\n",
    "                if root.left:\n",
    "                    dfs(root.left, val)\n",
    "                if root.right:\n",
    "                    dfs(root.right, val)\n",
    "                if not root.left and not root.right:\n",
    "                    nonlocal ans\n",
    "                    ans += val\n",
    "        \n",
    "        dfs(root, 0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = val = 0\n",
    "        st = []\n",
    "        pre = None\n",
    "        while root or st:\n",
    "            while root:\n",
    "                val = (val << 1) | root.val\n",
    "                st.append(root)\n",
    "                root = root.left\n",
    "            root = st[-1]\n",
    "            if root.right is None or root.right == pre:\n",
    "                if root.left is None and root.right is None:\n",
    "                    ans += val\n",
    "                val >>= 1\n",
    "                st.pop()\n",
    "                pre = root\n",
    "                root = None\n",
    "            else:\n",
    "                root = root.right\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(node, cur):\n",
    "            return ((cur << 1) + node.val if not node.left and not node.right else dfs(node.left, nxt := (cur << 1) + node.val) + dfs(node.right, nxt)) if node else 0\n",
    "        \n",
    "        return dfs(root, 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(root, path):\n",
    "            if not root:\n",
    "                return 0\n",
    "            path += str(root.val)\n",
    "            if not root.left and not root.right:\n",
    "                return int(path, 2)\n",
    "            return dfs(root.left, path) + dfs(root.right, path)\n",
    "        return dfs(root, '')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "\n",
    "        def recu(root, temp):\n",
    "            nonlocal ans\n",
    "            if root == None:\n",
    "                return\n",
    "            temp = temp * 2 + root.val\n",
    "            if root.left == None and root.right == None:\n",
    "                ans += temp\n",
    "            recu(root.left, temp)\n",
    "            recu(root.right, temp)\n",
    "        \n",
    "        recu(root, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(root,val):\n",
    "            if root is None:\n",
    "                return 0\n",
    "            val=(val<<1)|root.val\n",
    "            if root.left==None and root.right==None:\n",
    "                return val\n",
    "            return dfs(root.left,val)+dfs(root.right,val)   \n",
    "        return dfs(root,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(root: Optional[TreeNode], num: int) -> int:\n",
    "            ans = 0\n",
    "            if not root.left and not root.right:\n",
    "                ans = num << 1 | root.val\n",
    "            elif not root.left:\n",
    "                ans = dfs(root.right, num << 1 | root.val)\n",
    "            elif not root.right:\n",
    "                ans = dfs(root.left, num << 1 | root.val)\n",
    "            else:\n",
    "                ans = dfs(root.left, num << 1 | root.val) + dfs(root.right, num << 1 | root.val)\n",
    "            return ans\n",
    "        return dfs(root, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        total = 0\n",
    "        def dfs(root: TreeNode, pre_sum: int):\n",
    "            if not root:\n",
    "                return\n",
    "            current_sum = pre_sum * 2 + root.val\n",
    "            if not (root.left or root.right):\n",
    "                nonlocal total\n",
    "                total += current_sum\n",
    "                return \n",
    "            else:\n",
    "                dfs(root.left, current_sum)\n",
    "                dfs(root.right, current_sum)\n",
    "        \n",
    "        dfs(root, 0)\n",
    "\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        # 這題好難唷...\n",
    "        # recursive\n",
    "        def dfs(node, cur_sum):\n",
    "            if not node:\n",
    "                return 0\n",
    "            cur_sum = (2*cur_sum) + node.val\n",
    "            if not node.left and not node.right:\n",
    "                return cur_sum\n",
    "            return dfs(node.left, cur_sum) + dfs(node.right, cur_sum)\n",
    "        return dfs(root, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        # 這題好難唷...\n",
    "        # recursive (top-down)\n",
    "        \"\"\"\n",
    "        def dfs(node, cur_sum):\n",
    "            if not node: return 0\n",
    "\n",
    "            cur_sum = (2*cur_sum) + node.val # 要想到這點太難了...\n",
    "\n",
    "            if node.left or node.right:\n",
    "                return dfs(node.left, cur_sum) + dfs(node.right, cur_sum)\n",
    "            else:\n",
    "                return cur_sum\n",
    "        return dfs(root, 0)\n",
    "        \"\"\"\n",
    "\n",
    "        # iterative DFS\n",
    "        total_sum = 0\n",
    "        cur_sum   = 0\n",
    "        stack     = []\n",
    "        pre       = None\n",
    "        cur       = root\n",
    "\n",
    "        while cur or stack:\n",
    "            while cur:\n",
    "                cur_sum = (cur_sum*2) + cur.val\n",
    "                stack.append(cur)\n",
    "                cur = cur.left\n",
    "            \n",
    "            # 這裡已經沒有 left 了\n",
    "            cur = stack[-1]\n",
    "\n",
    "            if not cur.right or cur.right == pre:\n",
    "                if not cur.left and not cur.right:\n",
    "                    total_sum += cur_sum\n",
    "                cur_sum = cur_sum // 2 # 把最後一位踢掉\n",
    "                stack.pop()            # 把已經算完的這個 node 踢掉\n",
    "                pre = cur\n",
    "                cur = None\n",
    "            else:\n",
    "                cur = cur.right\n",
    "        return total_sum\n",
    "                \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        self.ans = 0\n",
    "        def dfs(node, num):\n",
    "            num = num * 2 + node.val\n",
    "            if node.left:\n",
    "                dfs(node.left, num)\n",
    "            if node.right:\n",
    "                dfs(node.right, num)\n",
    "            if not (node.left or node.right):\n",
    "                self.ans += num\n",
    "        \n",
    "        dfs(root, 0)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        def recur(pre_v,root):\n",
    "            pre_v=pre_v*2+root.val\n",
    "            if not root.left and not root.right:\n",
    "                self.result+=pre_v\n",
    "                return\n",
    "            if root.left:\n",
    "                recur(pre_v,root.left)\n",
    "            if root.right:\n",
    "                recur(pre_v,root.right)\n",
    "        \n",
    "        self.result=0\n",
    "        recur(0,root)\n",
    "        return self.result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        res = []\n",
    "        str_ = ''\n",
    "        def traversal(root, str_):\n",
    "            if not root:\n",
    "                return None\n",
    "            if not root.left and not root.right:\n",
    "                # str_ = ''.join(str(root.val))\n",
    "                str_ = str_+str(root.val)\n",
    "                res.append(str_)\n",
    "                str_ = ''\n",
    "            else:\n",
    "                # str_ = ''.join(str(root.val))\n",
    "                # nonlocal str_\n",
    "                str_ = str_ + str(root.val)\n",
    "            traversal(root.left, str_)\n",
    "            traversal(root.right, str_)\n",
    "        traversal(root, str_)\n",
    "        # print(res)\n",
    "        res = [int(i,2) for i in res]\n",
    "        # print(res)\n",
    "        return sum(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        def f(r, s):\n",
    "            if r:\n",
    "                s = s << 1 | r.val\n",
    "                if not r.left and not r.right:\n",
    "                    nonlocal ans\n",
    "                    ans += s\n",
    "                else:\n",
    "                    f(r.left, s)\n",
    "                    f(r.right, s)\n",
    "        f(root, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.path = 0\n",
    "        self.res = 0\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        self.traverse(root)\n",
    "        return self.res\n",
    "    def traverse(self,root):\n",
    "        if not root:\n",
    "            return\n",
    "        if not root.left and not root.right:\n",
    "            self.res += (self.path << 1) | root.val\n",
    "            return\n",
    "\n",
    "        self.path = (self.path << 1) | root.val\n",
    "        self.traverse(root.left)\n",
    "        self.traverse(root.right)\n",
    "        self.path >>=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def dfs(self, root, val, res):\n",
    "        if root is None:\n",
    "            return\n",
    "\n",
    "        val = (val << 1) + root.val\n",
    "        if root.left is None and root.right is None:\n",
    "            res.append(val)\n",
    "        else:\n",
    "            self.dfs(root.left, val, res)\n",
    "            self.dfs(root.right, val, res)\n",
    "\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        res = []\n",
    "        self.dfs(root, 0, res)\n",
    "\n",
    "        return sum(res)\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        path = []\n",
    "        res = []\n",
    "    \n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            path.append(str(root.val))\n",
    "            if not root.left and not root.right:\n",
    "                res.append(''.join(path))\n",
    "            dfs(root.left)\n",
    "            dfs(root.right)\n",
    "            path.pop()\n",
    "    \n",
    "        dfs(root)\n",
    "        ans = 0\n",
    "        for num in res:\n",
    "            # if len(num) <= 2:\n",
    "            #     ans += 1\n",
    "            # else:\n",
    "            #     cnt = collections.Counter(num)\n",
    "            #     if self.is_huiwen(cnt):\n",
    "            #         ans += 1\n",
    "            ans += int(num, 2)\n",
    "        return ans\n",
    "    #\n",
    "    # def is_huiwen(self, cnt):\n",
    "    #     if len(cnt) == 1:\n",
    "    #         return True\n",
    "    #     for _, val in cnt.items():\n",
    "    #         if val % 2 == 1:\n",
    "    #             return False\n",
    "    #     return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(root,val):\n",
    "            if not root:return 0\n",
    "            #将val向左移一位，然后最后一位与节点值进行与运算\n",
    "            val = (val << 1) | root.val\n",
    "            if root.left is None and root.right is None:\n",
    "                return val\n",
    "            return dfs(root.left,val) + dfs(root.right,val)\n",
    "        return dfs(root,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        self.res = 0\n",
    "\n",
    "        self.traverse(root, 0)\n",
    "\n",
    "        return self.res \n",
    "\n",
    "    def traverse(self, root, path_sum):\n",
    "        if root is None:\n",
    "            return \n",
    "\n",
    "        path_sum = (path_sum << 1) + root.val\n",
    "        if root.left is None and root.right is None:\n",
    "            self.res += path_sum \n",
    "\n",
    "        self.traverse(root.left, path_sum)\n",
    "        self.traverse(root.right, path_sum)\n",
    "\n",
    "        path_sum >>= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "\n",
    "        def dfs(node, val):\n",
    "\n",
    "            if not node: return 0\n",
    "\n",
    "            val = (val << 1) | node.val\n",
    "\n",
    "            if not node.left and not node.right:\n",
    "                return val\n",
    "            \n",
    "            return dfs(node.left, val) + dfs(node.right, val)\n",
    "        \n",
    "        return dfs(root, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def pre_order(node, parent_sum):\n",
    "\n",
    "    # 初始化 sum 值\n",
    "    sum = 0\n",
    "\n",
    "    # 节点为空，直接返回 sum\n",
    "    if node == None:\n",
    "        return sum\n",
    "\n",
    "    cur = (parent_sum << 1) | node.val\n",
    "    if node.left == None and node.right == None:\n",
    "        #  leaf 节点，将 cur 添加到 sum\n",
    "        sum += cur\n",
    "        # 直接返回，不需要后续操作\n",
    "        return sum\n",
    "\n",
    "    # 返回 left, right\n",
    "    sum += pre_order(node.left, cur)\n",
    "    sum += pre_order(node.right, cur)\n",
    "\n",
    "    # 返回结果\n",
    "    return sum\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: TreeNode) -> int:\n",
    "        return pre_order(root, 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        def f(r, s):\n",
    "            if r:\n",
    "                s = s << 1 | r.val\n",
    "                if not r.left and not r.right:\n",
    "                    nonlocal ans\n",
    "                    ans += s\n",
    "                else:\n",
    "                    f(r.left, s)\n",
    "                    f(r.right, s)\n",
    "        f(root, 0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        def dfs(root, r):\n",
    "            if root:\n",
    "                val = (r << 1) + root.val\n",
    "                if root.left:\n",
    "                    dfs(root.left, val)\n",
    "                if root.right:\n",
    "                    dfs(root.right, val)\n",
    "                if not root.left and not root.right:\n",
    "                    nonlocal ans\n",
    "                    ans += val\n",
    "        \n",
    "        dfs(root, 0)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ans = 0\n",
    "\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        self.dfs(root, str(root.val))\n",
    "        return self.ans\n",
    "\n",
    "\n",
    "    def dfs(self, node: Optional[TreeNode], bin_s):\n",
    "        if node.right:\n",
    "            self.dfs(node.right, bin_s + str(node.right.val))\n",
    "        if node.left:\n",
    "            self.dfs(node.left, bin_s + str(node.left.val))\n",
    "        if not node.left and not node.right:\n",
    "            self.ans += int(bin_s, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from functools import reduce\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        self.res = 0\n",
    "\n",
    "        self.traverse(root, [])\n",
    "\n",
    "        return self.res \n",
    "\n",
    "    def traverse(self, root, path):\n",
    "        if root is None:\n",
    "            return \n",
    "\n",
    "        path.append(root.val)\n",
    "\n",
    "        if root.left is None and root.right is None:\n",
    "            self.res += reduce(lambda x, y: x * 2 + y, path)\n",
    "\n",
    "        self.traverse(root.left, path)\n",
    "        self.traverse(root.right, path)\n",
    "\n",
    "        path.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        # 這題好難唷...\n",
    "        # recursive (top-down)\n",
    "        \"\"\"\n",
    "        def dfs(node, cur_sum):\n",
    "            if not node: return 0\n",
    "\n",
    "            cur_sum = (2*cur_sum) + node.val # 要想到這點太難了...\n",
    "\n",
    "            if node.left or node.right:\n",
    "                return dfs(node.left, cur_sum) + dfs(node.right, cur_sum)\n",
    "            else:\n",
    "                return cur_sum\n",
    "        return dfs(root, 0)\n",
    "        \"\"\"\n",
    "\n",
    "        # iterative DFS (這真的太難了...)\n",
    "        total_sum = 0\n",
    "        cur_sum   = 0\n",
    "        stack     = []\n",
    "        pre       = None\n",
    "        cur       = root\n",
    "\n",
    "        while cur or stack:\n",
    "            while cur:\n",
    "                cur_sum = (cur_sum*2) + cur.val\n",
    "                stack.append(cur)\n",
    "                cur = cur.left\n",
    "            \n",
    "            # 這裡已經沒有 left 了\n",
    "            cur = stack[-1]\n",
    "\n",
    "            # 沒有 right node\n",
    "            # 或者 right node 已經走過\n",
    "            if not cur.right or cur.right == pre:\n",
    "                if not cur.left and not cur.right:\n",
    "                    total_sum += cur_sum\n",
    "                cur_sum = cur_sum // 2 # 把最後一位踢掉\n",
    "                stack.pop()            # 把已經算完的這個 node 踢掉\n",
    "                pre = cur\n",
    "                cur = None\n",
    "            else:\n",
    "                cur = cur.right\n",
    "        return total_sum\n",
    "                \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#DFS\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(node, cur):\n",
    "            return ((cur << 1) + node.val if not node.left and not node.right else dfs(node.left, nxt := (cur << 1) + node.val) + dfs(node.right, nxt)) if node else 0\n",
    "        \n",
    "        return dfs(root, 0)\n",
    "\n",
    "\n",
    "#栈实现\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "\n",
    "        res = []\n",
    "        q = []\n",
    "        q.append([root, '0b'])  # 构建二进制的叶子结点字符串\n",
    "        while q:\n",
    "            node, tmp = q.pop(0)\n",
    "            tmp  += str(node.val)\n",
    "\n",
    "            if node.left:\n",
    "                q.append([node.left, tmp])\n",
    "            if node.right:\n",
    "                q.append([node.right, tmp])\n",
    "            \n",
    "            if not node.left and not node.right:\n",
    "                res.append(tmp)\n",
    "\n",
    "        return sum(int(bin_str, 2)   for bin_str in res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        def dfs(node, cur_sum):\n",
    "            if not node:\n",
    "                return 0\n",
    "            cur_sum = (cur_sum << 1) | node.val\n",
    "            if not node.left and not node.right:\n",
    "                return cur_sum\n",
    "            return dfs(node.left, cur_sum) + dfs(node.right, cur_sum)\n",
    "        return dfs(root, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        # 這題好難唷...\n",
    "        # recursive (top-down)\n",
    "        \"\"\"\n",
    "        def dfs(node, cur_sum):\n",
    "            if not node: return 0\n",
    "\n",
    "            cur_sum = (2*cur_sum) + node.val # 要想到這點太難了...\n",
    "\n",
    "            if node.left or node.right:\n",
    "                return dfs(node.left, cur_sum) + dfs(node.right, cur_sum)\n",
    "            else:\n",
    "                return cur_sum\n",
    "        return dfs(root, 0)\n",
    "        \"\"\"\n",
    "\n",
    "        # iterative DFS\n",
    "        total_sum = 0\n",
    "        cur_sum   = 0\n",
    "        stack     = []\n",
    "        pre       = None\n",
    "        cur       = root\n",
    "\n",
    "        while cur or stack:\n",
    "            while cur:\n",
    "                cur_sum = (cur_sum*2) + cur.val\n",
    "                stack.append(cur)\n",
    "                cur = cur.left\n",
    "            \n",
    "            # 這裡已經沒有 left 了\n",
    "            cur = stack[-1]\n",
    "\n",
    "            if not cur.right or cur.right == pre:\n",
    "                if not cur.left and not cur.right:\n",
    "                    total_sum += cur_sum\n",
    "                cur_sum = cur_sum // 2 # 把最後一位踢掉\n",
    "                stack.pop()            # 把已經算完的這個 node 踢掉\n",
    "                pre = cur\n",
    "                cur = None\n",
    "            else:\n",
    "                cur = cur.right\n",
    "        return total_sum\n",
    "                \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 0\n",
    "        def dfs(root, path):\n",
    "            if not root:\n",
    "                return\n",
    "            nonlocal res\n",
    "            path += str(root.val)\n",
    "            if not root.left and not root.right:\n",
    "                res += int(path, 2)\n",
    "                #print(res)\n",
    "            else:\n",
    "                dfs(root.left, path)\n",
    "                dfs(root.right, path)\n",
    "        dfs(root, '')\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        def dfs(root, path):\n",
    "            if not root:\n",
    "                return 0\n",
    "            path += str(root.val)\n",
    "            if not root.left and not root.right:\n",
    "                return int(path, 2)\n",
    "            return dfs(root.left, path) + dfs(root.right, path)\n",
    "        return dfs(root, '')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(node, v):\n",
    "            if node == None:\n",
    "                return 0\n",
    "            v = v << 1 | node.val\n",
    "            if not (node.right or node.left):\n",
    "                return v\n",
    "            return dfs(node.left, v) + dfs(node.right, v)\n",
    "\n",
    "        return dfs(root, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "[1,0,1,0,1,0,1]\n",
    "[1,0,1]\n",
    "[0]\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        res = [0]\n",
    "        self.dfs(root, 0, res)\n",
    "        return res[0]\n",
    "    def dfs(self, node, currSum, res):\n",
    "        if not node: return\n",
    "        currSum = (currSum << 1) | node.val\n",
    "        if not node.left and not node.right:\n",
    "            res[0] += currSum\n",
    "            return\n",
    "        self.dfs(node.left, currSum, res)\n",
    "        self.dfs(node.right, currSum, res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "\n",
    "        def dfs(node, val):\n",
    "\n",
    "            if not node:\n",
    "                return 0\n",
    "            val = (val << 1) | node.val\n",
    "            if not node.left and not node.right:\n",
    "                return val\n",
    "            return dfs(node.left, val) + dfs(node.right, val)\n",
    "        return dfs(root, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        def dg(root,num):\n",
    "            if not root:\n",
    "                return 0\n",
    "            num = (num << 1) | root.val\n",
    "            if not root.left and not root.right:\n",
    "                return num\n",
    "            return dg(root.left,num) + dg(root.right,num)\n",
    "        return dg(root,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.sum = 0\n",
    "\n",
    "    def dfs(self, node: Optional[TreeNode], cache: int) -> None:\n",
    "        binary = (cache << 1) | node.val\n",
    "        if node.left is None and node.right is None:\n",
    "            self.sum += binary\n",
    "            return\n",
    "\n",
    "        if node.left is not None:\n",
    "            self.dfs(node.left, binary)\n",
    "        if node.right is not None:\n",
    "            self.dfs(node.right, binary)\n",
    "\n",
    "        \n",
    "\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        self.dfs(root, 0)\n",
    "        return self.sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(root, num):\n",
    "            num = num << 1 | root.val\n",
    "            if not root.left and not root.right:\n",
    "                nonlocal res\n",
    "                res += num\n",
    "                return\n",
    "            if root.left:\n",
    "                dfs(root.left, num)\n",
    "            if root.right:\n",
    "                dfs(root.right, num)\n",
    "        res = 0\n",
    "        dfs(root, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: TreeNode) -> int:\n",
    "        def helper(node, value=\"\"):\n",
    "            if node is None:\n",
    "                return 0\n",
    "            if node.left is None and node.right is None:\n",
    "                return int(value + str(node.val), base=2)\n",
    "            else:\n",
    "                return helper(node.left, value + str(node.val)) + helper(node.right, value + str(node.val))\n",
    "\n",
    "        return helper(root)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        def traverse(node, res):\n",
    "            if node:\n",
    "                res = res * 2 + node.val\n",
    "                if not node.left and not node.right:\n",
    "                    return res\n",
    "                return traverse(node.left, res) + traverse(node.right, res)\n",
    "            return 0\n",
    "        return traverse(root, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        self.res = 0\n",
    "        self.path = 0\n",
    "        self.traverse(root)\n",
    "        return self.res\n",
    "    def traverse(self, root):\n",
    "        if root == None:\n",
    "            return\n",
    "        if root.left == None and root.right == None:\n",
    "            self.res += (self.path << 1) | root.val\n",
    "            return\n",
    "\n",
    "        self.path = (self.path << 1) | root.val\n",
    "        self.traverse(root.left)\n",
    "        self.traverse(root.right)\n",
    "        self.path >>= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 0\n",
    "        def helper(node, curr):\n",
    "            nonlocal res\n",
    "            if not node:\n",
    "                return\n",
    "            curr = curr*2 + node.val\n",
    "            if not node.left and not node.right:\n",
    "                res += curr\n",
    "            helper(node.left, curr)\n",
    "            helper(node.right, curr)\n",
    "        helper(root, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: TreeNode) -> int:\n",
    "        ans = 0\n",
    "        def f(r, s):\n",
    "            if r:\n",
    "                s = s * 2 + r.val\n",
    "                if not r.left and not r.right:\n",
    "                    nonlocal ans\n",
    "                    ans += s\n",
    "                else:\n",
    "                    f(r.left, s)\n",
    "                    f(r.right, s)\n",
    "        f(root, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        paths=[]\n",
    "        def construct_path(root,path):\n",
    "            if not root:\n",
    "                return \n",
    "            if root:\n",
    "                path=path+str(root.val)\n",
    "                if not root.left and not root.right:\n",
    "                    paths.append(int(path,2))\n",
    "                else:\n",
    "                    construct_path(root.left,path)\n",
    "                    construct_path(root.right,path)\n",
    "        construct_path(root,'')\n",
    "        return sum(paths)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        self.cur = 0\n",
    "        self.sum = 0\n",
    "        def travel(root):\n",
    "            if not root:\n",
    "                return \n",
    "            self.cur = self.cur*2 + root.val\n",
    "            travel(root.left)\n",
    "            travel(root.right)\n",
    "            if not root.left and not root.right:\n",
    "                self.sum += self.cur\n",
    "            self.cur = (self.cur - root.val)//2\n",
    "        travel(root)\n",
    "        return self.sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        def traverse(node,res):\n",
    "            if node is None:\n",
    "                return 0\n",
    "            res = res*2 + node.val\n",
    "            if node.left is None and node.right is None:\n",
    "                return res\n",
    "            else:\n",
    "                res = traverse(node.left,res)+traverse(node.right,res)\n",
    "            return res\n",
    "        return traverse(root,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(root, r):\n",
    "            ans = 0\n",
    "            if root:\n",
    "                val = (r << 1) + root.val\n",
    "                if root.left:\n",
    "                    ans += dfs(root.left, val)\n",
    "                if root.right:\n",
    "                    ans += dfs(root.right, val)\n",
    "                if not root.left and not root.right:\n",
    "                    ans += val\n",
    "            return ans\n",
    "        \n",
    "        return dfs(root, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 0\n",
    "        def dfs(root, path):\n",
    "            if not root:\n",
    "                return\n",
    "            nonlocal res\n",
    "            path += str(root.val)\n",
    "            if not root.left and not root.right:\n",
    "                res += int(path, 2)\n",
    "                #print(res)\n",
    "            else:\n",
    "                dfs(root.left, path)\n",
    "                dfs(root.right, path)\n",
    "        dfs(root, '')\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        def dfs(root, path):\n",
    "            if not root:\n",
    "                return 0\n",
    "            path += str(root.val)\n",
    "            if not root.left and not root.right:\n",
    "                return int(path, 2)\n",
    "            return dfs(root.left, path) + dfs(root.right, path)\n",
    "        return dfs(root, '')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(n: Optional[TreeNode], val: int):\n",
    "            if n is None:\n",
    "                return 0\n",
    "            r = (val << 1) | n.val\n",
    "            if n.left is None and n.right is None:\n",
    "                return r\n",
    "            return dfs(n.left, r) + dfs(n.right, r)\n",
    "        return dfs(root, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        path = []\n",
    "        val = 0\n",
    "        s = 0\n",
    "        def dfs(n: Optional[TreeNode]):\n",
    "            nonlocal s, val, path\n",
    "            if n is None:\n",
    "                return\n",
    "            path.append(n.val)\n",
    "            val = val * 2 + n.val\n",
    "            if n.left is None and n.right is None:\n",
    "                s += val\n",
    "                path.pop()\n",
    "                val = (val - n.val) // 2\n",
    "                return\n",
    "            if n.left:\n",
    "                dfs(n.left)\n",
    "            if n.right:\n",
    "                dfs(n.right)\n",
    "            path.pop()\n",
    "            val = (val - n.val) // 2\n",
    "        dfs(root)\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        self.result = []\n",
    "        def preorder(root,path):\n",
    "            if root:\n",
    "                path = path * 2 + root.val\n",
    "                if root.left is None and root.right is None:\n",
    "                    self.result.append(path)\n",
    "                preorder(root.left , path)\n",
    "                preorder(root.right , path)\n",
    "        preorder(root , 0)\n",
    "        return sum(self.result)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        ans = 0\n",
    "        def traverse(node, res):\n",
    "            nonlocal ans\n",
    "            if not node:\n",
    "                return\n",
    "            if not node.left and not node.right:\n",
    "                ans += int(''.join(str(i) for i in res + [node.val]), 2)\n",
    "                return\n",
    "\n",
    "            traverse(node.left, res + [node.val])\n",
    "            traverse(node.right, res + [node.val])\n",
    "            return\n",
    "        traverse(root, [])\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        self.nums = []\n",
    "        def dfs(node, currNum):\n",
    "            if not node:\n",
    "                return\n",
    "            currNum = currNum * 2 + node.val\n",
    "            if not node.left and not node.right:\n",
    "                self.nums.append(currNum)\n",
    "                return\n",
    "            dfs(node.left, currNum)\n",
    "            dfs(node.right, currNum)\n",
    "        dfs(root, 0)\n",
    "\n",
    "        return sum(self.nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "\n",
    "\n",
    "from typing import Optional\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(root: TreeNode, val) -> int:\n",
    "            if root is None:\n",
    "                return 0\n",
    "            res = (val << 1) | root.val\n",
    "            if root.left is None and root.right is None:\n",
    "                return res\n",
    "            return dfs(root.left, res) + dfs(root.right, res)\n",
    "\n",
    "        return dfs(root, 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(head, path):\n",
    "            nonlocal ans\n",
    "            if head != None:\n",
    "                path.append(str(head.val))\n",
    "                #print(path, ans)\n",
    "                if head.left == None and head.right == None:\n",
    "                    ans += int(''.join(path), 2)\n",
    "                dfs(head.left, path)\n",
    "                dfs(head.right, path)\n",
    "                path.pop()\n",
    "                return\n",
    "        path = []\n",
    "        ans = 0\n",
    "        dfs(root, path)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        return self.helper(root, 0)\n",
    "    def helper(self, root, ancestors):\n",
    "        if not root:\n",
    "            return 0\n",
    "        ancestors = ancestors * 2 + root.val\n",
    "        if not root.left and not root.right:\n",
    "            # root is a leaf\n",
    "            return ancestors\n",
    "        return self.helper(root.left, ancestors) + self.helper(root.right, ancestors)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:\n",
    "        def dfs(node: Optional[TreeNode], val: int) -> int:\n",
    "            if node is None:\n",
    "                return 0\n",
    "            val = (val << 1) | node.val   # |：按位或 ,<<左移就是*2，0左移1位还是0，累积该路径上的数值和\n",
    "            print(val, node.val)\n",
    "            if node.left is None and node.right is None:  # 叶子节点\n",
    "                return val\n",
    "            return dfs(node.left, val) + dfs(node.right, val) \n",
    "        return dfs(root, 0)\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
